package edu.nyu.hps.assignment1;

public class MintProblem {
	  
	int cost[] = new int[101];
	int coinSet1[] = new int[6];
	int coinSet2[] = new int[6];
	int currCoinSet[] = new int[6];
	int total1=100,total2=100;
	double N = 0.0;
	double exactChangeAvg = 100.00, smallChangeAvg = 100.00;
	int sum5 = 0, sumNot5 = 0;

	/**
	 * Constructor to input N
	 * @param n
	 */
	public MintProblem(double n){
		N = n;
	}
	
	/**
	 * Calculates the exact change of coins
	 */
	public void getExactChange() {
		for (int k = 0; k < cost.length; k++)
			cost[k] = 100;

		cost[0] = 0;
		cost[100] = 0;
		for (int i = 1; i < cost.length - 1; i++) {
			for (int j = 0; j < currCoinSet.length; j++) {
				if (currCoinSet[j] <= i
						&& (cost[i - currCoinSet[j]] + 1) < cost[i])
					cost[i] = cost[i - currCoinSet[j]] + 1;
			}
		}
	}

	/**
	 * Calculates best change of coins
	 */
	public void getSmallestChange() {
		for (int k = 0; k < cost.length; k++)
			cost[k] = 100;

		for (int k = 0; k < currCoinSet.length - 1; k++) {
			cost[currCoinSet[k]] = 1;
		}

		cost[0] = 0;
		cost[100] = 0;
		for (int i = 1; i < cost.length - 1; i++) {
			for (int j = 0; j < currCoinSet.length; j++) {
				if (currCoinSet[j] == i)
					break;
				else if (currCoinSet[j] > i) {
					cost[i] = Math.min(
							(cost[currCoinSet[j]] + cost[currCoinSet[j] - i]),
							(cost[currCoinSet[j - 1]] + cost[i
									- currCoinSet[j - 1]]));
					break;
				} else
					continue;
			}
		}
	}

	/**
	 * Calculates the weighted average
	 * @return weighted output
	 */
	public double getWeigthedAverage() {
		
		double sampleSpace = 1/((double)N*19 + 80);
		for (int i = 1; i < cost.length - 1; i++) {
			if (i % 5 != 0)
				sumNot5 += cost[i];
			else
				sum5 += cost[i];
		}
		double wAvg = (((double) sum5 * sampleSpace ) * N + ((double) sumNot5 *sampleSpace));
		return wAvg;
	}

	/**
	 * Main Functionality.
	 * Computes the weihted average for the exact or the best change
	 * which depends on N
	 */
	public void computeWeigthedAverage() {
		int i, j, k, l;//, m;
		double tempExactChgAvg, tempSmallChgAvg;
		currCoinSet[0] = 1;
		currCoinSet[5] = 100;

		for (i = 1; i < 50; i++) {
			currCoinSet[1] = i;
			for (j = i + 1; j < 50; j++) {
				currCoinSet[2] = j;
				for (k = j + 1; k < 50; k++) {
					currCoinSet[3] = k;
					for (l = k + 1; l < 50; l++) {
						currCoinSet[4] = l;
						getExactChange();
						tempExactChgAvg = getWeigthedAverage();
						if (tempExactChgAvg < exactChangeAvg) {
							exactChangeAvg = tempExactChgAvg;
							coinSet1 = currCoinSet.clone();
							total1  = sum5;
							total2 = sumNot5;
						}

						getSmallestChange();
						tempSmallChgAvg = getWeigthedAverage();
						if (tempSmallChgAvg < smallChangeAvg) {
							smallChangeAvg = tempSmallChgAvg;
							coinSet2 = currCoinSet.clone();
							total1  = sum5;
							total2 = sumNot5;
						}
					}
				}
			}		
		}

	}

	public int[] getCoinSet1() {
		return coinSet1;
	}

	public int[] getCoinSet2() {
		return coinSet2;
	}

	public double getExactChangeAvg() {
		return exactChangeAvg;
	}

	public double getSmallChangeAvg() {
		return smallChangeAvg;
	}
	
	public int getTotal1(){
		return total1;
	}	
	public int getTotal2(){
		return total2;
	}
}


